/*
** Routines to construction the finite state machine for the LEMON
** parser generator.
*/

#include "struct.h"
#include "set.h"
#include "config.h"
#include "symbol.h"
#include "configlist.h"
#include "action.h"
#include "error.h"
#include "lemon.h"

/* Find a precedence symbol of every rule in the grammar.
** 
** Those rules which have a precedence symbol coded in the input
** grammar using the "[symbol]" construct will already have the
** rp->precsym field filled.  Other rules take as their precedence
** symbol the first RHS symbol with a defined precedence.  If there
** are not RHS symbols with a defined precedence, the precedence
** symbol field is left blank.
*/
void FindRulePrecedences(Lemon *xp)
{
  for (Rule* rule : xp->rules) {
    if (rule->precsym == 0) {
      bool found = false;
      for (Symbol* sp : rule->rhs) {
        if (sp->type == MULTITERMINAL) {
          for (Symbol* subsp : sp->subsyms) {
            if (subsp->prec >= 0) {
              rule->precsym = subsp;
              found = true;
              break;
            }
          }
        } else if (sp->prec >= 0) {
          rule->precsym = sp;
          found = true;
        }
        if (found)
          break;
      }
    }
  }
  return;
}

/* Find all nonterminals which will generate the empty string.
** Then go back and compute the first sets of every nonterminal.
** The first set is the set of all terminal symbols which can begin
** a string generated by that nonterminal.
*/
void FindFirstSets(Lemon *lemp)
{
  for (int i=0; i<lemp->nsymbol; i++) {
    lemp->symbols[i]->lambda = false;
  }
  for (int i=lemp->nterminal; i < lemp->nsymbol; i++) {
    lemp->symbols[i]->firstset = SetNew();
  }

  int progress;
  /* First compute all lambdas */
  do{
    int i;
    progress = 0;
    for (Rule* rule : lemp->rules) {
      if (rule->lhs->lambda) continue;
      for (i=0; i < rule->rhs.size(); i++) {
        Symbol *sym = rule->rhs[i];
        assert(sym->type == NONTERMINAL || sym->lambda == false);
        if (sym->lambda == false) break;
      }
      if (i == rule->rhs.size()) {
        rule->lhs->lambda = true;
        progress = 1;
      }
    }
  }while (progress);

  /* Now compute all first sets */
  do{
    progress = 0;
    for (Rule* rule : lemp->rules) {
      Symbol *lsym = rule->lhs;
      for (Symbol* rsym : rule->rhs) {
        if (rsym->type == TERMINAL) {
          progress += SetAdd(lsym->firstset, rsym->index);
          break;
        } else if (rsym->type == MULTITERMINAL) {
          for (Symbol* sub : rsym->subsyms) {
            progress += SetAdd(lsym->firstset, sub->index);
          }
          break;
        } else if (lsym == rsym) {
          if (lsym->lambda == false) break;
        } else {
          progress += SetUnion(lsym->firstset, rsym->firstset);
          if (rsym->lambda == false) break;
        }
      }
    }
  }while (progress);
  return;
}

PRIVATE Symbol* FindStartSymbol(Lemon* lemp)
{
  Symbol* sym;
  /* Find the start symbol */
  if (lemp->start) { // %start_symbol
    sym = Symbol_find(lemp->start);
    if (sym == 0) {
      ErrorMsg(lemp->filename,0,
"The specified start symbol \"%s\" is not \
in a nonterminal of the grammar.  \"%s\" will be used as the start \
symbol instead.",lemp->start,lemp->startRule->lhs->name);
      lemp->errorcnt++;
      sym = lemp->startRule->lhs;
    }
  } else {
    sym = lemp->startRule->lhs;
  }

  /* Make sure the start symbol doesn't occur on the right-hand side of
  ** any rule.  Report an error if it does.  (YACC would generate a new
  ** start symbol in this case.) */
  for (Rule* rule : lemp->rules) {
    for (Symbol* rsym : rule->rhs) {
      if (sym == rsym) {   /* FIX ME:  Deal with multiterminals */
        ErrorMsg(lemp->filename,0,
"The start symbol \"%s\" occurs on the \
right-hand side of a rule. This will result in a parser which \
does not work properly.", sym->name);
        lemp->errorcnt++;
      }
    }
  }
  return sym;
}

/* Compute all LR(0) states for the grammar.  Links
** are added to between some states so that the LR(1) follow sets
** can be computed later.
*/
PRIVATE State *getstate(Lemon *);  /* forward reference */
void FindStates(Lemon *lemp)
{
  Symbol *start_sym = FindStartSymbol(lemp);

  /* The basis configuration set for the first state
  ** is all rules which have the start symbol as their
  ** left-hand side */
  for (Rule* rule : start_sym->rules) {
    rule->lhsStart = 1;
    Config *newcfp = Configlist_addbasis(rule, 0);
    SetAdd(newcfp->fws,0);
  }

  /* Compute the first state.  All other states will be
  ** computed automatically during the computation of the first one.
  ** The returned pointer to the first state is not used. */
  (void)getstate(lemp);
  return;
}

/* Return a pointer to a state which is described by the configuration
** list which has been built from calls to Configlist_add.
*/
PRIVATE void buildshifts(Lemon *, State *); /* Forwd ref */
PRIVATE State *getstate(Lemon *lemp)
{
  /* Extract the sorted basis of the new state.  The basis was constructed
  ** by prior calls to "Configlist_addbasis()". */
  Configlist_sortbasis();
  ConfigList& basis = Configlist_basis();

  /* Get a state with the same basis */
  State* state = lemp->FindState(basis);
  if (state) {
    /* A state with the same basis already exists!  Copy all the follow-set
    ** propagation links from the state under construction into the
    ** preexisting state, then return a pointer to the preexisting state */
    auto x = basis.begin();
    auto y = state->basis_configs.begin();
    for (; x != basis.end() && y != state->basis_configs.end(); ++x, ++y) {
      (*y)->bplp.splice((*y)->bplp.begin(), (*x)->bplp);
      (*x)->fplp.clear();
      (*x)->bplp.clear();
    }
    ConfigList& configs = Configlist_return();
    Configlist_eat(configs);
  } else {
    /* This really is a new state.  Construct all the details */
    Configlist_closure(lemp);    /* Compute the configuration closure */
    Configlist_sort();           /* Sort the configuration closure */
    ConfigList& configs = Configlist_return();   /* Get a pointer to the config list */
    state = new State;           /* A new state structure */
    MemoryCheck(state);
    state->basis_configs = std::move(basis);    /* Remember the configuration basis */
    state->configs = std::move(configs);       /* Remember the configuration closure */
    lemp->AddState(state, state->basis_configs);   /* Add to the state table */
    buildshifts(lemp,state);       /* Recursively compute successor states */
  }
  return state;
}

/*
** Return true if two symbols are the same.
*/
int same_symbol(Symbol *a, Symbol *b)
{
  if (a == b) return 1;
  if (a->type != MULTITERMINAL) return 0;
  if (b->type != MULTITERMINAL) return 0;
  if (a->subsyms != b->subsyms)
    return 0;

  return 1;
}

/* Construct all successor states to the given state.  A "successor"
** state is any state which can be reached by a shift action.
*/
PRIVATE void buildshifts(Lemon *lemp, State *state)
{
  Symbol *sp;   /* Symbol following the dot in configuration "cfp" */
  Symbol *bsp;  /* Symbol following the dot in configuration "bcfp" */

  /* Each configuration becomes complete after it contibutes to a successor
  ** state.  Initially, all configurations are incomplete */
  for (Config* conf : state->configs) conf->status = INCOMPLETE;

  /* Loop through all configurations of the state "state" */
  for (auto it = state->configs.begin(); it != state->configs.end(); ++it) {
    Config* cfp = *it;
    if (cfp->status==COMPLETE) continue;    /* Already used by inner loop */
    if (cfp->dot >= cfp->rp->rhs.size()) continue;  /* Can't shift this config */
    Configlist_reset();                      /* Reset the new config set */
    sp = cfp->rp->rhs[cfp->dot];             /* Symbol after the dot */

    /* For every configuration in the state "state" which has the symbol "sp"
    ** following its dot, add the same configuration to the basis set under
    ** construction but with the dot shifted one symbol to the right. */
    for (auto jt = it; jt != state->configs.end(); ++jt) {
      Config* bcfp = *jt;
      if (bcfp->status == COMPLETE) continue;    /* Already used */
      if (bcfp->dot >= bcfp->rp->rhs.size()) continue; /* Can't shift this one */
      bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */
      if (!same_symbol(bsp,sp)) continue;      /* Must be same as for "cfp" */
      bcfp->status = COMPLETE;                  /* Mark this config as used */
      Config* newcfg = Configlist_addbasis(bcfp->rp, bcfp->dot+1);
      newcfg->bplp.push_front(bcfp);
    }

    /* Get a pointer to the state described by the basis configuration set
    ** constructed in the preceding loop */
    State *newstate = getstate(lemp);

    /* The state "newstate" is reached from the state "state" by a shift action
    ** on the symbol "sp" */
    if (sp->type == MULTITERMINAL) {
      for (Symbol* subsp : sp->subsyms) {
        Action_add(state->actions, SHIFT, subsp, (char*)newstate);
      }
    } else {
      Action_add(state->actions, SHIFT, sp, (char*)newstate);
    }
  }
}

/*
** Construct the propagation links
*/
void FindLinks(Lemon *lemp)
{
  /* Housekeeping detail:
  ** Add to every propagate link a pointer back to the state to
  ** which the link is attached. */
  for (State* state : lemp->sorted_states) {
    for (Config* conf : state->configs) {
      conf->stp = state;
    }
  }

  /* Convert all backlinks into forward links.  Only the forward
  ** links are used in the follow-set computation. */
  for (State* state : lemp->sorted_states) {
    for (Config* conf : state->configs) {
      for (Config* other : conf->bplp) {
        other->fplp.push_front(conf);
      }
    }
  }
}

/* Compute all followsets.
**
** A followset is the set of all symbols which can come immediately
** after a configuration.
*/
void FindFollowSets(Lemon *lemp)
{
  int progress;
  int change;

  for (State* state : lemp->sorted_states) {
    for (Config* cfp : state->configs) cfp->status = INCOMPLETE;
  }
  
  do {
    progress = 0;
    for (State* state : lemp->sorted_states) {
      for (Config* cfp : state->configs) {
        if (cfp->status == COMPLETE) continue;
        for (Config* xcfg : cfp->fplp) {
          change = SetUnion(xcfg->fws, cfp->fws);
          if (change) {
            xcfg->status = INCOMPLETE;
            progress = 1;
          }
        }
        cfp->status = COMPLETE;
      }
    }
  } while (progress);
}

static int resolve_conflict(Action *,Action *);

/* Compute the reduce actions, and resolve conflicts.
*/
void FindActions(Lemon *lemp)
{
  /* Add all of the reduce actions 
  ** A reduce action is added for each element of the followset of
  ** a configuration which has its dot at the extreme right.
  */
  for (State* state : lemp->sorted_states) {
    for (Config* cfp : state->configs) {  /* Loop over all configurations */
      if (cfp->rp->rhs.size() == cfp->dot) {        /* Is dot at extreme right? */
        for (int j=0; j < lemp->nterminal; j++) {
          if (SetFind(cfp->fws,j)) {
            /* Add a reduce action to the state "stp" which will reduce by the
            ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
            Action_add(state->actions, REDUCE, lemp->symbols[j], (char*)cfp->rp);
          }
        }
      }
    }
  }

  Symbol *sym;
  /* Add the accepting token */
  if (lemp->start) {
    sym = Symbol_find(lemp->start);
    if (sym == 0) sym = lemp->startRule->lhs;
  } else {
    sym = lemp->startRule->lhs;
  }
  /* Add to the first state (which is always the starting state of the
  ** finite state machine) an action to ACCEPT if the lookahead is the
  ** start nonterminal.  */
  Action_add(lemp->sorted_states[0]->actions, ACCEPT, sym, 0);

  /* Resolve conflicts */
  for (State* stp : lemp->sorted_states) {
    /* assert( stp->ap ); */
    std::list<Action*>& actions = stp->actions;
    Action_sort(actions);
    for (auto i = actions.begin(); i != std::prev(actions.end()); ++i) {
      for (auto j = std::next(i); j != actions.end() && (*i)->sp == (*j)->sp; ++j) {
         /* The two actions "ap" and "nap" have the same lookahead.
         ** Figure out which one should be used */
         lemp->nconflict += resolve_conflict(*i, *j);
      }
    }
  }

  /* Report an error for each rule that can never be reduced. */
  for (Rule* rule : lemp->rules) rule->canReduce = false;
  for (State* state : lemp->sorted_states) {
    for (Action* ap : state->actions) {
      if (ap->type==REDUCE) ap->x.rp->canReduce = true;
    }
  }
  for (Rule* rule : lemp->rules) {
    if (rule->canReduce) continue;
    ErrorMsg(lemp->filename,rule->ruleline,"This rule can not be reduced.\n");
    lemp->errorcnt++;
  }
}

/* Resolve a conflict between the two given actions.  If the
** conflict can't be resolved, return non-zero.
**
** NO LONGER TRUE:
**   To resolve a conflict, first look to see if either action
**   is on an error rule.  In that case, take the action which
**   is not associated with the error rule.  If neither or both
**   actions are associated with an error rule, then try to
**   use precedence to resolve the conflict.
**
** If either action is a SHIFT, then it must be apx.  This
** function won't work if apx->type==REDUCE and apy->type==SHIFT.
*/
static int resolve_conflict(Action *apx, Action *apy)
{
  Symbol *spx, *spy;
  int errcnt = 0;
  assert( apx->sp==apy->sp );  /* Otherwise there would be no conflict */
  if (apx->type==SHIFT && apy->type==SHIFT) {
    apy->type = SSCONFLICT;
    errcnt++;
  }
  if (apx->type==SHIFT && apy->type==REDUCE) {
    spx = apx->sp;
    spy = apy->x.rp->precsym;
    if (spy==0 || spx->prec<0 || spy->prec<0) {
      /* Not enough precedence information. */
      apy->type = SRCONFLICT;
      errcnt++;
    } else if (spx->prec>spy->prec) {    /* higher precedence wins */
      apy->type = RD_RESOLVED;
    } else if (spx->prec<spy->prec) {
      apx->type = SH_RESOLVED;
    } else if (spx->prec==spy->prec && spx->assoc==RIGHT) { /* Use operator */
      apy->type = RD_RESOLVED;                             /* associativity */
    } else if (spx->prec==spy->prec && spx->assoc==LEFT) {  /* to break tie */
      apx->type = SH_RESOLVED;
    } else {
      assert( spx->prec==spy->prec && spx->assoc==NONE );
      apx->type = ERROR;
    }
  } else if (apx->type==REDUCE && apy->type==REDUCE) {
    spx = apx->x.rp->precsym;
    spy = apy->x.rp->precsym;
    if (spx==0 || spy==0 || spx->prec<0 ||
    spy->prec<0 || spx->prec==spy->prec) {
      apy->type = RRCONFLICT;
      errcnt++;
    } else if (spx->prec>spy->prec) {
      apy->type = RD_RESOLVED;
    } else if (spx->prec<spy->prec) {
      apx->type = RD_RESOLVED;
    }
  } else {
    assert( 
      apx->type==SH_RESOLVED ||
      apx->type==RD_RESOLVED ||
      apx->type==SSCONFLICT ||
      apx->type==SRCONFLICT ||
      apx->type==RRCONFLICT ||
      apy->type==SH_RESOLVED ||
      apy->type==RD_RESOLVED ||
      apy->type==SSCONFLICT ||
      apy->type==SRCONFLICT ||
      apy->type==RRCONFLICT
    );
    /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
    ** REDUCEs on the list.  If we reach this point it must be because
    ** the parser conflict had already been resolved. */
  }
  return errcnt;
}
